package 搜索算法.广度优先搜索;

import java.util.*;

/**
 * 1. 问题描述
 *      给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}


@SuppressWarnings("all")
public class 二叉树的遍历2 {
    public static void main(String[] args) {

    }

    /**
     * 队列实现的广度优先遍历  我采用的是数组构成的队列   官方的效率高
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom1(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>(); // 存放每层元素的容器
        if(root == null) {
            return ans;
        }
        Deque<TreeNode> deque = new ArrayDeque<>(); // 创建队列
        deque.offer(root); // 初始化，root节点入队
        while(!deque.isEmpty()) { // 队空循环结束
            int nodesize = deque.size(); // 获取当前对中节点数
            List<Integer> temp = new ArrayList<>();
            for(int i = 0; i < nodesize; i++) {
                TreeNode cur = deque.removeFirst();
                temp.add(cur.val);
                if(cur.left != null) {
                    deque.addLast(cur.left);
                }
                if(cur.right != null) {
                    deque.addLast(cur.right);
                }
            }
            ans.add(temp);
        }
        List<List<Integer>> res = new ArrayList<>();
        for(int i = ans.size()-1; i >= 0; i--) {
            res.add(ans.get(i));
        }
        return res;
    }

    /**
     * 官方采用的链式结构构成的队列
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom2(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }


}
